/*
 * @lc app=leetcode.cn id=1046 lang=golang
 * @lcpr version=30119
 *
 * [1046] 最后一块石头的重量
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start
type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func lastStoneWeight(stones []int) int {
	pq := &MaxHeap{}

	for i := 0; i < len(stones); i++ {
		*pq = append(*pq, stones[i])
	}

	heap.Init(pq)

	for pq.Len() > 1 {
		a := heap.Pop(pq).(int)
		b := heap.Pop(pq).(int)

		if a != b {
			heap.Push(pq, a-b)
		}
	}
	if pq.Len() == 0 {
		return 0
	}
	return heap.Pop(pq).(int)
}

// @lc code=end

/*
// @lcpr case=start
// [2,7,4,1,8,1]\n
// @lcpr case=end

*/

